package day28;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/11/28 21:12
 */

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 *
 *
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 *
 * 输入：head = []
 * 输出：[]
 */
public class Solution5 {
    public ListNode sortList(ListNode head) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while (head!=null){
            pq.add(head.val);
            head = head.next;
        }
        return pre(pq);
    }
    public ListNode pre(PriorityQueue<Integer> pq){
        if(pq.isEmpty()){
            return null;
        }
        ListNode listNode = new ListNode(pq.poll());
        listNode.next=pre(pq);
        return listNode;
    }
}
